Techniques for designing layouts that comply with ground rules and grid constraints include compaction and minimum layout perturbation (MinPert) based legalization. The compaction technique minimizes the area of the layout by relocating objects while satisfying rules and constraints. This technique is based on the longest path algorithm. There are known compaction techniques for flat layouts with ground rules, ground rules and single grid constraints, and ground rules with multiple grid constraints. There are also known compaction techniques for hierarchical layouts with ground rules. However, the compaction technique does not handle multiple grid constraints for a hierarchical layout. Furthermore, the iteration bound which is used to check whether there is a feasible compaction solution to satisfy the given constraints (e.g., whether there is a positive cycle in the grid longest path) is not accurate.
MinPert-based legalization is an alternative to compaction, as disclosed in U.S. Pat. No. 6,189,132, which is hereby incorporated by reference in its entirety. Unlike the traditional compaction technique, which mainly considers area minimization, MinPert-based legalization attempts to improve a given layout by correcting ground rule violations while changing the original layout as little as possible. MinPert-based legalization is advantageous because it addresses cases with conflicting rules that cause positive cycles and cannot be handled by the conventional compaction techniques. MinPert-based legalization does not address grid constraints.
Solutions exist for legalization of a flat layout with critical grid constraints (e.g., grid constraints where only the transistors (e.g., critical gates) are required to be on the grid), and for legalization of flat and hierarchical designs with multiple grid constraints. An example of critical grid constraint legalization for a flat layout (or leaf cell) is shown in FIGS. 1a and 1b. In this example, the layout of the cell consists of two gates where polysilicon-conductor shapes intersect with diffusion shapes. Before legalization, as shown in FIG. 1a, the left edges of the gates (the placement of which is shown by the distances from the origin of the cell to the left edges of the gate, d1 and d2) are not aligned on the pre-defined grid 10. After legalization, as shown in FIG. 1b, though, the left edges of the gates (the placement of which is shown by the revised distances e1 and e2) have both been moved such that they are placed on the grid 10.
In contrast, an example of legalization for a hierarchical layout with critical grid constraints is shown in FIGS. 2a and 2b. In order to legalize a hierarchical layout with critical grid constraints, not only the edges of the gates but also the transforms of the instances have to be moved in order to place the gates on the grid. And, the hierarchical constraints (that is, consistent placement results among all instances of the same model or cell) must also be maintained. As can be seen in FIGS. 2a and 2b, a cell consists of two gates which are placed at distance of d1 and d2from the cell origin, and the hierarchical layout includes two instances of the cell and the transforms of these instances T1 and T2. Before legalization, as shown in FIG. 2a, the left edges of the gates are not aligned on the pre-defined grid 10. The grid constraints are:d2−d1=P; and(T2+d1)−(T1+d2)=P, where P is the pitch of the grid. From these constraints it can be seen that:(T2−T1)=P+(d2−d1).If the transforms are fixed and given and T2−T1≠2P, then it can be seen that it is impossible to satisfy both the first and the second constraints. Thus, the transforms must be moved to the solution as graphically shown in FIG. 2b. Solutions for such hierarchical designs including critical grid constraints, though, do not currently exist.